Công ty được thành lập vào năm 1965 (đăng ký chính thức tháng 9 năm 1966) tại thị trấn Kotanopan, thuộc huyện Mandailing Natal, Bắc Sumatra. Những người sáng lập công ty là bảy thương gia nông sản có mối quan hệ gia đình, ban đầu công ty sử dụng hai chiếc xe tải Chevrolet được chuyển đổi cho tuyến Kotanopan đến Medan.[2][3] Khi công ty phát triển, hãng thiết lập dịch vụ Medan đến Bukittinggi, và đến năm 1972 hãng có các tuyến phục vụ các thành phố lớn khác ở Sumatra như Bandar Lampung, Jambi, Palembang và Padang. Công ty chuyển trụ sở chính đến Medan.[4]

ALS bắt đầu phục vụ các tuyến đến Java trong những năm 1970, trước khi thiết lập các dịch vụ RORO giữa Java và Sumatra. Tuy nhiên, do thiếu tàu có khả năng chuyên chở phương tiện vào thời điểm đó, ALS thỏa thuận với các công ty phà để vận chuyển hành khách từ Bakauheni đến Merak. Khi có dịch vụ phà RORO, ALS mở rộng danh sách các nơi đến từ Java, tới Malang và Jember ở Đông Java và kéo dài đến Bali.[5]